package 分类.一维动规;

public class 最长公共子串 {
    public static String LCS (String s1, String s2) {
        // write code here
        if(s1.length()==0||s2.length()==0){
            return "-1";
        }
        int m=s1.length();
        int n=s2.length();
        int[][] dp=new int[m+1][n+1];
        dp[0][0]=0;
        int maxlen=0;
        int last=0;
        for (int i=1;i<=m;i++){
            for (int j=1;j<=n;j++){
                    if(s1.charAt(i-1)==s2.charAt(j-1)){
                        dp[i][j]=1+dp[i-1][j-1];
                        if(dp[i][j]>maxlen){
                            maxlen=dp[i][j];
                            last=i-1;
                        }
                    }else {
                        dp[i][j]=0;
                    }

            }
        }
        return s1.substring(last-maxlen+1,last+1);
    }

    public static void main(String[] args) {
        String a="1AB2345CD",b="12345EF";
        System.out.println(LCS(a, b));
    }

}
